// C++11 thread库的使用
#include <iostream>
#include <vector>
#include <thread>
#include <mutex>
#include <atomic>
#include <condition_variable>
#include <chrono>
#include <unistd.h>

// 条件变量
// 基于条件变量，实现2个线程分别交替打印奇数和偶数
std::condition_variable cond;
std::mutex mt;
bool flag = true;

int main()
{
    std::thread t1([](){
        int i = 0;
        while(i < 100) {
            std::unique_lock<std::mutex> lock(mt);
            while(!flag) cond.wait(lock);
            std::cout << i << std::endl;
            i += 2;
            flag = false;
            cond.notify_one();
        }
    });

    std::thread t2([](){
        int j = 1;
        while(j < 100) {
            std::unique_lock<std::mutex> lock(mt);
            while(flag) cond.wait(lock);
            std::cout << j << std::endl;
            j += 2;
            flag = true;
            cond.notify_one();
        }
    });

    t1.join();
    t2.join();

    return 0;
}


// 自旋锁
// 当临界区资源很少，即线程持有锁的时间极短时，如果此时仍使用互斥锁，当一个线程切换上下文还没完时，就释放锁了
// 而自旋锁，避免了传统互斥锁中线程阻塞 / 唤醒的上下文切换开销（这是一个相对昂贵的操作）。
// 自旋等待的时间远小于线程切换的时间（通常为微秒级 vs 毫秒级）。
class SpinLock {
private:
    // 原子标志，初始化为false（未锁定状态）
    std::atomic_flag flag = ATOMIC_FLAG_INIT;
    // 等价于std::atomic<bool> 

public:
    // 锁定：循环尝试设置标志，直到成功（获取锁）
    void lock() {
        // test_and_set：原子地设置flag为true，并返回之前的值
        // 若之前为false（未锁定），则获取锁成功，退出循环
        while (flag.test_and_set(std::memory_order_acquire)) {
            // 空循环自旋（忙等）
        }
    }

    // 解锁：清除标志（释放锁）
    void unlock() {
        // 清除flag为false，memory_order_release保证内存可见性
        flag.clear(std::memory_order_release);
    }
};



//  compare_exchange_weak() 与 compare_exchange_strong() 实现无锁编程
//  两者的参数一致，判断方法也一致：如果当前值与期望值相等，则将新值赋给当前值，并且返回true
//                               如果当前值与期望值不同，即该值已经被其他线程改了，此时修改期望值为当前值，并返回false
// 但是因为硬件原因，~weak有可能会出现假失败，即期望值与当前值一致，却返回false
// 出现这种情况一般要进行循环重试

// 一个简单的无锁链表
// a simple global linked list:
struct Node { int value; Node* next; };
std::atomic<Node*> list_head (nullptr);

void append (int val) {     // append an element to the list
  Node* oldHead = list_head; // 期望值
  Node* newNode = new Node {val,oldHead}; // 新值，并链接在期望值头部

  // what follows is equivalent to: list_head = newNode, but in a thread-safe way:
  // 当只有一个线程下来时，当前值就是期望值，此时直接让当前值等于新值，返回true，退出循环
  // 当有多个线程下来时，期望值都是一个，但新值有多个，但总会有先后顺序去执行循环
  // 先执行到循环的，就跟一个线程一样，替换完后推出循环
  // 后执行的，此时比较时，当前值已经被更新了，但期望值还没变，此时就会更新期望值，返回false进入循环
  // 让他自己的新值，链到当前值的头部
  // 初始值：liss_head = 0
  // old_head = 0
  // t1：new_node_1
  // t2: new_node_2
  // t1先执行CAS： list_head == old_head, list_head = new_node_1 -> 0
  // t2再执行CAS:  list_head == new_node_1 != 0, 
  //              old_head = new_node_1, 进入循环
  //              new_node_2 -> new_node_1 -> 0
  //              再次判断：
  //               list_head = old_node = new_node_1，此时更新list_head = new_node_2
  //                list_head = new_node_2 -> new_node_1 -> 0
  while (!list_head.compare_exchange_weak(oldHead,newNode))
    newNode->next = oldHead;
}

int main1 ()
{
  // spawn 10 threads to fill the linked list:
  // 创建10个线程，分别将自己的序号头插到链表中
  std::vector<std::thread> threads;
  for (int i=0; i<10; ++i) threads.push_back(std::thread(append,i));
  for (auto& th : threads) th.join();

  // print contents:
  for (Node* it = list_head; it!=nullptr; it=it->next)
    std::cout << ' ' << it->value;
  std::cout << '\n';

  // cleanup:
  Node* it; while (it=list_head) {list_head=it->next; delete it;}

  return 0;
}

//std::atomic<int> counter;
//// std::atomic_int counter 由atomic<int> typedef
//
//void free_lock_add()
//{
//    for(int i=0; i<10000; i++) {
//        int old_val = counter.load(); // 记录当前值
//
//        // compare_exhange_weak 比较并交换，如果counter值与old_val一致，则将counter改变为old_val+1 ,返回true
//        // 如果不一致，则将old_val变为counter的当前值 ,返回false
//        // 这也是原子++的实现原理，即counter++
//        while(!counter.compare_exchange_weak(old_val, old_val+1));
//        // if(counter.compare_exchange_strong(old_val, old_val+1))
//    }
//}
//
//int main()
//{
//    counter.store(0); // 将counter的值设为1
//    std::cout << counter.load() << std::endl; // 读取counter的内容
//
//    int num_threads = 4;
//    std::vector<std::thread> threads;
//    for (int i = 0; i < num_threads; ++i) {
//        threads.emplace_back(free_lock_add);
//    }
//  
//    for (auto& t : threads) {
//        t.join();
//    }
//
//    std::cout << counter.load() << std::endl; // 读取counter的内容
//
//    return 0;
//}

//std::atomic<int> acnt;
//int cnt;
//
//void increment(int n) {
//    for (int i = 0; i < n; ++i) {
//        acnt++; // 原子自增，无需加锁
//        cnt++; 
//    }
//}
//
//int main() {
//    const int num_threads = 4;
//    const int increments_per_thread = 100000;
//    
//    std::vector<std::thread> threads;
//    for (int i = 0; i < num_threads; ++i) {
//        threads.emplace_back(increment, increments_per_thread);
//    }
//    
//    for (auto& t : threads) {
//        t.join();
//    }
//    
//    // 预期结果：4 * 100000 = 400000
//    std::cout << "Final counter value: " << acnt << std::endl;
//    std::cout << "Final counter value: " << cnt << std::endl;
//    return 0;
//}


//std::atomic<bool> ready (false);
//std::atomic_flag winner = ATOMIC_FLAG_INIT;
//
//void count1m (int id) {
//  while (!ready) { std::this_thread::yield(); }      // wait for the ready signal
//  for (volatile int i=0; i<1000000; ++i) {}          // go!, count to 1 million
//  if (!winner.test_and_set()) { std::cout << "thread #" << id << " won!\n"; }
//};
//
//int main ()
//{
//  std::vector<std::thread> threads;
//  std::cout << "spawning 10 threads that count to 1 million...\n";
//  for (int i=1; i<=10; ++i) threads.push_back(std::thread(count1m,i));
//  ready = true;
//  for (auto& th : threads) th.join();
//
//  return 0;
//}


// std::call_once example
// 可变参模板函数
// template <class Fn, class... Args>
// void call_once (once_flag& flag, Fn&& fn, Args&&... args);
// 第一个参数为标志位，fn为可调用对象，args参数包表示给该fn传递的参数
// call_once使得该可调用对象在多线程h环境下，只被执行一次
//int winner;
//void set_winner (int x) { winner = x; }
//std::once_flag winner_flag;
//
//void wait_1000ms (int id) {
//  // count to 1000, waiting 1ms between increments:
//  for (int i=0; i<1000; ++i)
//    std::this_thread::sleep_for(std::chrono::milliseconds(1));
//  // claim to be the winner (only the first such call is executed):
//  std::call_once (winner_flag,set_winner,id);
//}
//
//int main ()
//{
//  std::thread threads[10];
//  // spawn 10 threads:
//  for (int i=0; i<10; ++i)
//    threads[i] = std::thread(wait_1000ms,i+1);
//
//  std::cout << "waiting for the first among 10 threads to count 1000 ms...\n";
//
//  for (auto& th : threads) th.join();
//  std::cout << "winner thread: " << winner << '\n';
//
//  return 0;
//}
//

// std::try_lock example
// try_lock也是可变模板函数，可以同时锁住多个锁
// 当申请多个锁时，如果那个锁没有被申请到，try_lock会释放掉已经申请的锁，并返回申请锁时锁的下标(锁从0开始计数)
// 如果所有的锁都已经锁住了，则会返回-1
//std::mutex foo,bar;
//
//void task_a () {
//  foo.lock();
//  std::cout << "task a\n";
//  bar.lock();
//  // ...
//  foo.unlock();
//  bar.unlock();
//}
//
//void task_b () {
//  int x = try_lock(bar,foo);
//  if (x==-1) {
//    std::cout << "task b\n";
//    // ...
//    bar.unlock();
//    foo.unlock();
//  }
//  else {
//    std::cout << "[task b failed: mutex " << (x?"foo":"bar") << " locked]\n";
//  }
//}
//
//int main ()
//{
//  std::thread th1 (task_a);
//  std::thread th2 (task_b);
//
//  th1.join();
//  th2.join();
//
//  return 0;
//}


// std::lock example
// 可变参数模板函数, 可以同时锁住多个锁
// 当申请多个锁失败后，会先释放已经锁住的锁，然后在没有锁住的锁上阻塞
//std::mutex foo,bar;
//
//void task_a () {
//  // foo.lock(); bar.lock(); // replaced by:
//  std::lock (foo,bar);
//  std::cout << "task a\n";
//  foo.unlock();
//  bar.unlock();
//}
//
//void task_b () {
//  // bar.lock(); foo.lock(); // replaced by:
//  std::lock (bar,foo);
//  std::cout << "task b\n";
//  bar.unlock();
//  foo.unlock();
//}
//
//int main ()
//{
//  std::thread th1 (task_a);
//  std::thread th2 (task_b);
//
//  th1.join();
//  th2.join();
//
//  return 0;
//}

//std::mutex mtx;
//void Print()
//{
//    //std::lock_guard<std::mutex> lock(mtx);
//    mtx.lock();
//    std::lock_guard<std::mutex> lock(mtx, std::adopt_lock); // 使用adopt_lock时，意味着互斥锁已经锁住了，lock_guard只是对互斥锁进行管理
//    //std::unique_lock<std::mutex> lock(mtx);
//    std::cout << std::this_thread::get_id() << std::endl;
//    std::cout << std::this_thread::get_id() << std::endl;
//    std::cout << std::this_thread::get_id() << std::endl;
//    std::cout <<"\n";
//}
//
//
//int main()
//{
//    std::thread threads[2];
//    for(int i=0; i<2; i++)
//        threads[i] = std::thread(Print);
//    for(int i=0; i<2; i++)
//        threads[i].join();
//    return 0;
//}

//void Print(int i, int &x, std::mutex &mtx)
//{
//    mtx.lock();
//    while(i--) {
//        x++;
//    }
//    mtx.unlock();
//}
//
//int main()
//{
//    // 当线程的入口函数使用局部变量时，为了避免线程安全问题，我们需要传互斥锁进去
//    // 但是因为互斥锁不支持拷贝，所以我们得传引用
//    // 在这里传引用时，我们要使用ref()函数
//    int x = 0;
//    std::mutex mtx;
//
//    std::thread t1(Print, 1000000, std::ref(x), std::ref(mtx));
//    std::thread t2(Print, 1000000, std::ref(x), std::ref(mtx));
//
//    t1.join();
//    t2.join();
//    std::cout << x << std::endl;
//}

// 线程入口函数使用全局变量和全局锁
//std::mutex _mutex;
//int x = 0;
//
//void Print(int n)
//{
//    _mutex.lock();
//    while(n--) {
//        //std::cout << std::this_thread::get_id() << " thread running" << std::endl;
//        x++;
//    }
//    _mutex.unlock();
//}
//
//int main()
//{
//    std::thread t1(Print, 1000000);
//    std::thread t2(Print, 2000000);
//
//    t1.join();
//    t2.join();
//    std::cout << x << std::endl;
//    return 0;
//}

//void routine1() 
//{
//    std::cout << "t1 thread id -> " << std::this_thread::get_id() << std::endl;
//}
//
//void routine2()
//{
//    std::cout << "t2 thread id -> " << std::this_thread::get_id() << std::endl;
//}
//
//int main()
//{
//    // 可以使用swap方法，交换两个线程对象底层所使用的线程
//    std::thread t1(routine1);
//    std::thread t2(routine2);
//
//    std::cout << "t1 thread id-> " << t1.get_id() << std::endl;
//    std::cout << "t2 thread id-> " << t2.get_id() << std::endl;
//    t1.swap(t2);
//    std::cout << "t1 thread id-> " << t1.get_id() << std::endl;
//    std::cout << "t2 thread id-> " << t2.get_id() << std::endl;
//
//    t1.join();
//    t2.join();
//
//    return 0;
//}

//void routine()
//{
//    std::cout << "i am  a new thread -> " << std::this_thread::get_id() << std::endl;
//}
//
//void Print(int begin, int end)
//{
//    for(;begin < end; begin++)
//    {
//        std::cout << begin << std::endl;
//    }
//}

//int main()
//{
//    std::thread t1(routine);
//    std::thread t2(Print, 0, 10);
//    std::thread t3([](){
//        std::cout << " i am a new thread ->" << std::this_thread::get_id() << std::endl;
//    });
//
//    // join用来回收子线程资源，如果子线程结束了，但是没有被主线程回收，就会进入僵尸，导致资源泄露
//    //t1.join();
//    //t2.join();
//    //t3.join();
//
//    // 但其实为了避免未定义的行为，在进行join或者detach之前，我们必须得先判断线程是否是可连接的
//    // joinable返回true的情况：
//    //     1.线程还没有被join
//    //     2.线程还没有被detach
//    //     3.线程对象底层有对应的线程，即创建时分配了线程的函数入口
//    // joinable返回false的情况：
//    //     1.当线程已经被join
//    //     2.线程已经被detach
//    //     3.线程对象底层并没有绑定的线程
//    if(t1.joinable())
//        t1.join();
//    if(t2.joinable())
//        t2.join();
//    if(t3.joinable())
//        t3.join();
//    return 0;
//}